package com.wzq.solution.node;

class Solution42 {
    public static  int trap(int[] height) {
        
        int len = height.length;
        if(len==0 || len==1){
            return 0;
        }
        int top1=0;
        int top2=0;
        
        for(int i=0;i<len;i++){
            if(height[i]>top1){
                top2=top1;
                top1=height[i];
            }else if(height[i]>top2){
                top2=height[i];
            }
        }
        
        int rst = 0;
        int notZeroStart = 0;
        int notZeroEnd = len-1;
        do{
            while(height[notZeroStart] == 0){
                notZeroStart++;
            }
            while(height[notZeroEnd] == 0){
                notZeroEnd--;
            }
            
            int min = 1;
            
            for(int j=notZeroStart; j<=notZeroEnd; j++){
                if(height[j] >0 && height[j]< min){
                    min = height[j];
                }
            }
            
            for(int j=notZeroStart; j<=notZeroEnd; j++){
                if(height[j] == 0){
                    rst += min;
                }else{
                    height[j] -= min;
                }
            }
            top2 -= min;
        }while(top2 > 0);
        
        return rst;
    }




    public static int trap1(int[] nums){
        if(nums.length < 2){
            return 0;
        }
        int rst=0;
        int leftMax=0,rightMax=0;
        int left=0;
        int right=nums.length-1;
        while (left<right){
            if(nums[left] < nums[right]){
                if(nums[left] < leftMax){
                    rst += leftMax-nums[left];
                }else{
                    leftMax = nums[left];
                }
                left++;
            }else{
                if(nums[right] < rightMax){
                    rst += rightMax-nums[right];
                }else{
                    rightMax=nums[right];
                }
                right--;
            }
        }
        return rst;
    }
    public static int trap2(int[] nums) {
        if (nums.length < 1) return 0;
        int left_max=0,right_max=0,res=0;
        int left=0, right=nums.length-1;

        while(left<right) {
            if (nums[left] < nums[right]) {
                if (nums[left] < left_max)
                    res += left_max - nums[left];
                else
                    left_max = nums[left];
                left++;
            }else{
                if (nums[right] < right_max)
                    res += right_max - nums[right];
                else
                    right_max = nums[right];
                right--;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[] heights = new int[]{
                10527,740,9013,1300,29680,4898,13993,15213,
                18182,24254,3966,24378,11522,9190,6389,32067,
                21464,7115,7760,3925,31608,16047,20117,239,14254,3647,11664,27710,2374,23076,5655,9035,4725,13013      };
        int rst = trap1(heights);
        System.out.println(rst);
        rst = trap2(heights);
        System.out.println(rst);
    }
}